A Hybrid Representation proposed in Okabe, T., Jin, Y. and Sendhoff, B. Evolutionary Multi-Objective Optimisation with a Hybrid Representation, In Proceedings of Congress on Evolutionary Computation (CEC-2003), pages 2262-2269, 2003, which is incorporated by reference in its entirety, is exploiting the different dynamics of Genetic Algorithm (GA) and Evolution Strategy (ES). This difference is caused by the different offspring distribution. The new algorithm shows superior performance compared to the state-of-the-art MOO methods. A natural for the extension of the Hybrid Representation algorithm is to try to model the optimal offspring distribution directly. This new algorithm generates a stochastic model from the offspring distribution in the Parameter Space (PS). Based on this stochastic model, offspring will be generated. Neither crossover nor mutation are used. This type of algorithms is often called Estimation of Distribution Algorithm (EDA). FIG. 1 shows the difference between EAs (a) and EDAs (b) as it is known from conventional systems. Besides the way how they generate offspring, both of them are basically the same.
Genetic Algorithms (GAs) are well known to be powerful tools to obtain optimal solutions for complex optimization problems. As an extension of GAs, recently Estimation of Distribution Algorithms (EDAs) have received considerable attention, see Tsutsui, et al, cited below. The first authors to use the term “EDA” for estimating the distribution of promising points were Mühlenbein and Paass. In the state of the art, several EDAs have been proposed. Since the research for EDAs was triggered by the problem of disruption in GA, a lot of methods are suitable for discrete problems only. However, recently, several papers for the continuous problem have been also published.
According to a recent survey of EDAs, Pelikan, M., Goldberg, D. E. and Lobo, F. A Survey of Optimization by Building and Using Probabilistic Models. Technical Report 99018, University of Illinois, Urbana-Champaign Urbana, Ill. 61801, 1999 which is incorporated by reference herein in its entirety, the proposed methods can be classified into three classes: (1) no interaction, (2) pairwise interaction, and (3) multivariable interaction.
The first class, i.e. no interaction, does not consider any epistasis at all. Thus, each locus is treated independently. The second class, i.e., pairwise interaction, considers pairwise dependency only. Finally, multivariable interaction takes into account any type of dependency between variables.
The classification of the state of the art EDA methods can be seen in the following Table 1-a for discrete domains and in Table 1-b for continuous domains. All of the references cited in these tables are incorporated by reference herein in their entirety.
TABLE 1-aEDA methods for discrete domains.1) NoUnivariate MarginalMühlenbein, H. and Mahnig, T. EvolutionaryInteractionDistributionAlgorithms: From Recombination to SearchAlgorithm (UMDA)Distributions. In Theoretical Aspects of EvolutionaryComputing, pages 135-173, 2000, andMühlenbein, H. and Mahnig, T. Evolutionary Synthesisof Bayesian Networks for Optimization. Advances inEvolutionary Synthesis of Intelligent Agent, pages 429-455,2001.Population BasedBaluja, S. Population-Based Incremental Learning: AIncremental LearningMethod for Integrating Genetic Search Based Function(PBIL)Optimization and Competitive Learning. TechnicalReport CMU-CS-94-163, Carnegie Mellon University,1994.Compact GeneticHarik, G. R., Lobo, F. G. and Goldberg, D. E. TheAlgorithm (cGA)Compact Genetic Algorithm. Technical Report 97006,University of Illinois, Urbana-Champaign Urbana, IL61801, 1997, andHarik, G. R., Lobo, F. G. and Goldberg, D. E. TheCompact Genetic Algorithm. In Proceedings ofCongress on Evolutionary Computation (CEC-1998),pages 523-528, 1998.Hill-Climing withKvasnicka, V., Pelikan, M. and Pospichal, J. HillLearning (HCwL)Climbing with Learning (An Abstraction of GeneticAlgorithm). Neural Network World, 6: 773-796, 1996.IncrementalMühlenbein, H. The Equation for the Response toUnivariate MarginalSelection and Its Use for Prediction. EvolutionaryDistributionComputation, 5(3): 303-346, 1998.Algorithm (IUMDA)ReinforcementPaul, T. K. and Iba, H. Reinforcement LearningLearning EstimationEstimation of Distribution Algorithm. In Proceedings ofof DistributionGenetic and Evolutionary Computation ConferenceAlgorithm (RELEDA)(GECCO-2003), pages 1259-1270, 2003.2) PairwiseMutual Informationde Bonet, J. S., Isbell, J., Charles, L. and Viola, P.InteractionMaximization forMIMIC: Finding Optima by Estimating ProbabilityInput ClusteringDensities. Advances in Neural Information Processing(MIMIC)Systems, 9: 424-431, 1996.CombiningBaluja, S. and Davies, S. Combining MultipleOptimizers withOptimization Runs with Optimal Dependency Trees.Mutual InformationTechnical Report CMU-CS-97-157, Carnegie MellonTrees (COMIT)University, 1997.Bivariate MarginalMühlenbein, H. and Mahnig, T. Evolutionary SynthesisDistributionof Bayesian Networks for Optimization. Advances inAlgorithm (BMDA)Evolutionary Synthesis of Intelligent Agent, pages 429-455,2001, andPelikan, M. and Mühlenbein, H. Marginal Distributionsin Evolutionary Algorithms. In Proceedings of the ForthInternational Conference on Genetic Algorithms(Mendel-1998), pages 90-95, 1998.3) Multi-Extended CompactHarik, G. R. Linkage Learning via ProbabilisticvariableGenetic AlgorithmModeling in the ECGA. Technical Report 99010,Interaction(ECGA)University of Illinois, Urbana-Champaign Urbana, IL61801, 1999, andLobo, F. G. and Harik, G. R. Extended Compact GeneticAlgorithm in C++. Technical Report 99016, Universityof Illinois, Urbana-Champaign Urbana, IL 61801, 1999.FactorizedMühlenbein, H. and Mahnig, T. FDA - A ScalableDistributionEvolutionary Algorithm for the Optimization ofAlgorithm (FDA)Additively Decomposed Functions. EvolutioanryComputation, 7(1): 45-68, 1999, andMühlenbein, H. and Mahnig, T. The FactorizedDistribution Algorithm for Additively DecomposedFunctions. In Proceedings of Congress on EvolutionaryComputation (CEC-1999), pages 752-759, 1999, andMühlenbein, H. and Mahnig, T. Evolutionary Synthesisof Bayesian Networks for Optimization. Advances inEvolutionary Synthesis of Intelligent Agent, pages 429-455,2001.PolytreeLarrañaga, P. and Lozano, J. A., editor. Estimation ofApproximatin ofDistribution Algorithms. A New Tool for EvolutionaryDistributionComputation. Kluwer Academic Publishers, 2002.Algorithm (PADA)Estimation ofLarrañaga, P., Etxeberria, R., Lozano, J. A. and Pena, J. M.Bayesian NetworksOptimization by Learning and Simulation ofAlgorithm (EBNA)Bayesian and Gaussian Networks. Technical ReportEHU-KZAA-IK-4/99, Department of Computer Scienceand Artificial Intelligence, University of the BasqueCountry, 1999.BayesianKhan, N., Goldberg, D. E. and Pelikan, M. Multi-Optimizationobjective Bayesian Optimization Algorithm. TechnicalAlgorithm (BOA)Report 2002009, Univeristy of Illinois, Uvbana-Champaign, Urbana, IL 61801, 2002, andLaumanns, M. and Ocenasek, J. Bayesian OptimizationAlgorithms for Multi-objective Optimization. InProceedings of Parellel Problem Solving from NatureVII (PPSN-VII), pages 298-307, 2002, andPelikan, M., Goldberg, D. E. and Cantu-Pax, E. BOA:The Bayesian Optimization Algorithm. In Proceedingsof Genetic and Evolutionary Computation Conference(GECCO-1999), pages 525-532, 1999, andPelikan, M., Goldberg, D. E. and Cantu-Paz, E. LinkageProblem, Distribution Estimation and BayesianNetworks. Technical Report 98013, University ofIllinois, Urbana-Champaign Urbana, IL 61801, 1998,andPelikan, M., Goldberg, D. E. and Cantu-Paz, E. BOA:The Bayesian Optimization Algorithm. TechnicalReport 99003, University of Illinois, Urbana-ChampaignUrbana, IL 61801, 1999, andZhang, B.-T. A Bayesian Framework for EvolutionaryComputation. In Proceedings of Congress onEvolutionary Computation (CEC-1999), pages 722-728,1999.Learning FactorizedMühlenbein, H. and Mahnig, T. Evolutionary SynthesisDistributionof Bayesian Networks for Optimization. Advances inAlgorithm (LFDA)Evolutionary Synthesis of Intelligent Agent, pages 429-455,2001.FactorizedLarrañaga, P. and Lozano, J. A., editor. Estimation ofDistributionDistribution Algorithms. A New Tool for EvolutionaryAlgorithm (FDA)Computation. Kluwer Academic Publishers, 2002.(extended version)
TABLE 1-bEDA methods for continuous domains.1) NoUnivariate MarginalLarrañaga, P., Etxeberria, R., Lozano, J. A. and Peña,InteractionDistributionJ. M. Optimization by Learning and Simulation ofAlgorithm (UMDAC)Bayesian and Gaussian Networks. Technical ReportEHU-KZAA-IK-4/99, Department of Computer Scienceand Artificial Intelligence, University of the BasqueCountry, 1999.Stochastic HillRudlof, S. and Köppen, M. Stochastic Hill ClimbingClimbing withwith Learning by Vectors of Normal Distributions. InLearning by VectorsProceedings of the First Online Workshop on Softof NormalComputing (WSC1), Nagoya, Japan, 1997.Distributions(SHCLVND)Population BasedSebag, M. and Ducoulombier, A. Extending Population-Incremental LearningBased Incremental Learning to Continuous Search(PBILC)Spaces. In Proceedings of Parallel Problem Solvingfrom Nature V (PPSN-V), pages 418-427, 1998.2) PairwiseMutual InformationLarrañaga, P., Etxeberria, R., Lozano, J. A. and Peña,InteractionMaximization forJ. M. Optimization by Learning and Simulation ofInput ClusteringBayesian and Gaussian Networks. Technical Report(MIMICC)EHU-KZAA-IK-4/99, Department of Computer Scienceand Artificial Intelligence, University of the BasqueCountry, 1999.3) MultivariableEstimation ofLarrañaga, P. and Lozano, J. A., editor. Estimation ofInteractionMultivariate NormalDistribution Algorithms. A New Tool for EvolutionaryAlgorithm (EMNA)Computation. Kluwer Academic Publishers, 2002.Estimation ofLarrañaga, P. and Lozano, J. A., editor. Estimation ofGaussian NetworksDistribution Algorithms. A New Tool for EvolutionaryAlgorithm (EGNA)Computation. Kluwer Academic Publishers, 2002.Iterated DensityBosman, P. A. N. and Thierens, D. An AlgorithmicEstimation AlgorithmFramework for Density Estimation Based Evolutionary(IDEA)Algorithms. Technical Report UU-CS-1999-46,Department of Computer Science, Utrecht University,1999, andBosman, P. A. N. and Thierens, D. Continuous IteratedDensity Estimation Evolutionary Algorithms within theIDEA Framework. Technical Report UU-CS-2000-15,Department of Computer Science, Utrecht University,2000, andBosman, P. A. N. and Thierens, D. IDEAs Based on theNormal Kernels Probability Density Function. TechnicalReport UU-CS-2000-11, Department of ComputerScience, Utrecht University, 2000, andBosman, P. A. N. and Thierens, D. Mixed IDEAs.Technical Report UU-CS-2000-45, Department ofComputer Science, Utrecht University, 2000, andBosman, P. A. N. and Thierens, D. Negative Log-Likelihood and Statistical Hypothesis Testing as theBasis of Model Selection in IDEAs. In Proceedings ofthe Tenth Belgium-Netherlands Conference on MachineLearning, pages 109-116, 2000, andBosman, P. A. N. and Thierens, D. AdvancingContinuous IDEAs with Mixture Distributions andFactorization Selection Metrics. In Proceedings of theOptimization by Building and using ProbabilisticModels OBUPM Workshop at the Genetic andEvolutionary Computation Conference (GECCO-2001),pages 208-212, 2001, andThierens, D. and Bosmann, P. A. N. Multi-ObjectiveMixture-based Iterated Density Estimation EvolutionaryAlgorithms. In Proceedings of Genetic and EvolutionaryComputation Conference (GECCO-2001), pages 663-670,2001.Parzen Estimation ofCosta, M. and Minisci, E. MOPED: A Multi-objectiveDistributionParzen-based Estimation of Distribution Algorithm forAlgorithm (PEDA)Continuous Problems. In Proceedings of the SecondInternational Conference on Evolutionary Multi-Criterion Optimization (EMO-2003), pages 282-294,2003.Marginal HistgramTsutsui, S., Pelikan, M. and Goldberg, D. E.Model (MHM)Probabilistic Model-building Genetic Algorithms UsingMarginal Histograms in Continuous Domain. InProceedings of the KES-2001, Knowledge-basedIntelligent Information Engineering Systems and AlliedTechnologies, volume 1, pages 112-121, andTsutsui, S., Pelikan, M. and Goldberg, D. E.Evolutionary Algorithm Using Marginal HistogramModels in Continuous Domain. Technical Report2001019, University of Illinois, Urbana-ChampaignUrbana, IL 61801, 2001.
Since the method proposed by the present invention belongs to the class of multivariable interaction, some of the popular methods in this category will be explained next.
To learn the linkage among parameters and therefore the structure of the problem, Bayesian networks are used. With the Bayesian Networks, the conditional probability is approximated. Each node and connection in the Bayesian networks correspond to the parameters and the conditional probability, respectively. Finally, the factorized probability is used to generate offspring. Recently, this method has been applied to MOO problems and has gathered much attention as per Khan, N., Goldberg, D. E. and Pelikan, M. Multi-objective Bayesian Optimization Algorithm. Technical Report 2002009, Univeristy of Illinois, Urbana-Champaign, Urbana, Ill. 61801, 2002 and Laumanns, M. and Ocenasek, J. Bayesian Optimization Algorithms for Multi-objective Optimization. In Proceedings of Parellel Problem Solving from Nature VII (PPSN-VII), pages 298-307, 2002 which are incorporated by reference herein in their entirety. Iterated Density Estimation Evolutionary Algorithm (IDEA)
Bosman and Thierens have proposed four types of EDAs that all belong to the class of IDEA. The first one is for the discrete domain where the conditional probability is used to build up the stochastic model. The others are for the continuous domain. A normalized Gaussian, a histogram method and a kernel method are used to generate the stochastic model. The kernel based method has been also applied to MOO, called Mixture-based IDEA (MIDEA).
Parzen-Based Estimation of Distribution Algorithm (PEDA)
To generate the stochastic model, a Parzen estimator is used to approximate the probability density of solutions. Based on the stochastic model, new offsprings will be generated. This method has been used for MOO problems.
Marginal Histogram Model (MHM)
For each parameter, the search space is divided into small bins. The ratio of the number of individuals in each bin to the whole number is assigned as the selection probability. With this probability, a bin is selected randomly. In the selected bin, an offspring is generated uniformly.
In view of these references, it is the object of the present invention to propose a more efficient algorithm for optimization.